package com.suxin.algorithm.graph;

import java.util.Arrays;

/**
 * @author Tang
 * @classname DJSTL
 * @description [ 最短路径 ]
 * @date 2023/1/16 22:18
 */
public class DJSTL_ {

    /**
     * 地图
     */
    public final static int[][] MAP = new int[][]{
            {0,1,12,-1,-1},
            {-1,0,9,3,-1},
            {-1,-1,0,-1,5},
            {-1,-1,4,0,13},
            {-1,-1,-1,-1,0}
    };

    public int[] disct = new int[5];

    /**
     * 标记数组：用来标记那些点已经被使用过了
     */
    public boolean[] marker = new boolean[5];

    public void djsl() {
        // 初始化第一个点的距离
        for (int i = 0; i < 5; i++) {
            disct[i] = MAP[0][i];
            if (disct[i] == -1) {
                disct[i] = Integer.MAX_VALUE;
            }
        }
        int i = 1;
        while (i < 5) {
            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            // 从disct数组找到距离当前点最近点的位置
            for (int i1 = 1; i1 < disct.length; i1++) {
                if (!marker[i1] && disct[i1] != -1 && disct[i1] < min) {
                    min = disct[i1];
                    minIndex = i1;
                }
            }
            System.out.println("min: " + minIndex);
            marker[minIndex] = true;
            for (int i1 = 1; i1 < MAP[i].length; i1++) {
                // MAP[minIndex][i1] + disct[minIndex] < disct[i1]
                // 当前最短路径到达其他点的距离 + 当前已知最短路径点的距离 < 原点直接到这个点的距离
                if (MAP[i][i1] != -1 && MAP[minIndex][i1] != -1
                        && (MAP[minIndex][i1] + disct[minIndex] < disct[i1])) {
                    disct[i1] = MAP[minIndex][i1] + disct[minIndex];
                }
            }
            i++;
        }
    }

    public static void main(String[] args) {
        DJSTL_ djstl_ = new DJSTL_();
        djstl_.djsl();
        System.out.println("最短路径：" + Arrays.toString(djstl_.disct));
    }

}
